//
// Created by mazaiting on 2024/4/27.
//
#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct LinkNode            //单链表结点类型
{
    T data;                        //存放数据元素
    LinkNode<T> *next;                //下一个结点的指针
    LinkNode() : next(NULL) {}            //构造函数
    explicit LinkNode(T d) : data(d), next(NULL) {}        //重载构造函数
};

template<typename T>
class LinkList            //单链表类模板
{
public:
    LinkNode<T> *head;        //单链表头结点

    LinkList()          //构造函数,创建一个空单链表
    {
        head = new LinkNode<T>();
    }

    ~LinkList()           //析构函数,销毁单链表
    {
        LinkNode<T> *pre, *p;
        pre = head;
        p = pre->next;
        while (p != NULL)       //用p遍历结点并释放其前驱结点
        {
            delete pre;           //释放pre结点
            pre = p;
            p = p->next;       //pre,p同步后移一个结点
        }
        delete pre;           //p为空时pre指向尾结点,此时释放尾结点
    }

//基本运算算法

    void CreateListF(T a[], int n)            //头插法建立单链表
    {
        for (int i = 0; i < n; i++)            //循环建立数据结点
        {
            auto *s = new LinkNode<T>(a[i]);//创建数据结点s
            s->next = head->next;            //将结点s插入head结点之后
            head->next = s;
        }
    }

    void CreateListR(T a[], int n)        //尾插法建立单链表
    {
        LinkNode<T> *s, *r;
        r = head;                //r指向尾结点,开始时指向头结点
        for (int i = 0; i < n; i++)        //循环建立数据结点
        {
            s = new LinkNode<T>(a[i]);            //创建数据结点s
            r->next = s;            //将结点s插入结点r之后
            r = s;
        }
        r->next = NULL;            //将尾结点的next域置为NULL
    }

    LinkNode<T> *geti(int i)             //返回序号i的结点
    {
        if (i < -1) return NULL;             //i<-1返回NULL
        LinkNode<T> *p = head;        //首先p指向头结点
        int j = -1;            //j置为-1(可以认为头结点序号为-1)
        while (j < i && p != NULL)             //指针p移动i+1个结点
        {
            j++;
            p = p->next;
        }
        return p;            //返回p
    }

    void Add(T e)                    //在单链表末尾添加一个值为e的结点
    {
        auto *s = new LinkNode<T>(e);    //新建结点s
        LinkNode<T> *p = head;
        while (p->next != NULL)        //查找尾结点p
            p = p->next;
        p->next = s;                //在尾结点之后插入结点s
    }

    int Getlength()            //求单链表中数据结点个数
    {
        LinkNode<T> *p = head;
        int cnt = 0;
        while (p->next != NULL)        //找到尾结点为止
        {
            cnt++;
            p = p->next;
        }
        return cnt;
    }

    bool GetElem(int i, T &e)        //求单链表中序号i的结点值
    {
        if (i < 0) return false;        //参数i错误返回false
        LinkNode<T> *p = geti(i);        //查找序号i的结点
        if (p != NULL)                    //找到了序号i的结点p
        {
            e = p->data;
            return true;            //成功找到返回true
        } else                    //不存在序号i的结点
            return false;            //参数i错误返回false
    }

    bool SetElem(int i, T e)        //设置序号i的结点值
    {
        if (i < 0) return false;        //参数i错误返回false
        LinkNode<T> *p = geti(i);        //查找序号i的结点
        if (p != NULL)                    //找到了序号i的结点p
        {
            p->data = e;
            return true;
        } else                    //不存在序号i的结点
            return false;            //参数i错误返回false
    }

    int GetNo(T e)                //查找第一个为e的元素的序号
    {
        int j = 0;                //j置为0，p指向首结点
        LinkNode<T> *p = head->next;
        while (p != NULL && p->data != e)             //查找第一个值为e的结点p
        {
            j++;
            p = p->next;
        }
        if (p == NULL) return -1;                 //未找到时返回-1
        else return j;                     //找到后返回其序号
    }

    bool Insert(int i, T e)                 //在序号i位置插入值为e的结点
    {
        if (i < 0) return false;                 //参数i错误返回false
        auto *s = new LinkNode<T>(e);       //建立新结点s
        LinkNode<T> *p = geti(i - 1);        //查找序号i-1的结点
        if (p != NULL)                     //找到了序号i-1的结点p
        {
            s->next = p->next;                 //在p结点后面插入s结点
            p->next = s;
            return true;            //插入成功返回true
        } else                    //没有找到序号i-1的结点
            return false;            //参数i错误返回false
    }

    bool Delete(int i)          //在单链表中删除序号i位置的结点
    {
        if (i < 0) return false;               //参数i错误返回false
        LinkNode<T> *p = geti(i - 1);      //查找序号i-1的结点
        if (p != NULL)                   //找到了序号i-1的结点p
        {
            LinkNode<T> *q = p->next;      //q指向序号i的结点(被删结点)
            if (q != NULL)          //存在序号i的结点时删除它
            {
                p->next = q->next;               //删除p结点的后继结点
                delete q;          //释放空间
                return true;          //删除成功返回true
            } else              //没有找到序号i的结点
                return false;               //参数i错误返回false
        } else                  //没有找到序号i-1的结点
            return false;          //参数i错误返回false
    }

    void DispList()                //输出单链表所有结点值
    {
        LinkNode<T> *p;
        p = head->next;            //p指向开始结点
        while (p != NULL)            //p不为NULL,输出p结点的data域
        {
            cout << p->data << " ";
            p = p->next;            //p移向下一个结点
        }
        cout << endl;
    }

};

template<typename T>
T Middle1(LinkList<T> &L)         //求解算法1
{
    int j = 1;
    int n = L.Getlength();
    LinkNode<T> *p = L.head->next;         //p指向首结点
    while (j <= (n - 1) / 2)             //找中间位置的p结点
    {
        j++;
        p = p->next;
    }
    return p->data;
}

template<typename T>
int Maxcount(LinkList<T> &L)            //求解算法
{
    int cnt = 1;
    LinkNode<T> *p = L.head->next;            //p指向首结点
    T maxe = p->data;                //maxe置为首结点值
    while (p->next != NULL)            //循环到p结点为尾结点
    {
        if (p->next->data > maxe)            //找到更大的结点
        {
            maxe = p->next->data;            //第一次找到maxe的结点
            cnt = 1;
        } else if (p->next->data == maxe)        //p结点为当前最大值结点
            cnt++;                        //次数增1
        p = p->next;
    }
    return cnt;
}

template<typename T>
void Delmaxnodes(LinkList<T> &L)        //求解算法
{
    LinkNode<T> *p = L.head->next;        //p指向首结点
    T maxe = p->data;            //maxe置为首结点值
    while (p->next != NULL)            //查找最大结点值maxe
    {
        if (p->next->data > maxe)
            maxe = p->next->data;
        p = p->next;
    }
    LinkNode<T> *pre = L.head;        //pre指向头结点
    p = pre->next;                //p指向pre的后继结点
    while (p != NULL)            //p遍历所有结点
    {
        if (p->data == maxe)            //p结点为最大值结点
        {
            pre->next = p->next;        //删除p结点
            delete p;
            p = pre->next;            //让p指向pre的后继结点
        } else {
            pre = pre->next;            //pre后移一个结点
            p = pre->next;            //让p指向pre的后继结点
        }
    }
}

template<typename T>
void Reverse1(LinkList<T> &L)        //求解算法1
{
    LinkNode<T> *p = L.head->next, *q;    //p指向首结点
    L.head->next = NULL;            //将L置为一个空表
    while (p != NULL)            //用p遍历所有数据结点
    {
        q = p->next;            //q临时保存p结点的后继结点
        p->next = L.head->next;        //将p结点插入到表头
        L.head->next = p;
        p = q;
    }
}

template<typename T>
void Reverse2(LinkList<T> &L)        //求解算法2
{
    LinkNode<T> *p = L.head->next, *q, *r;       //p指向首结点
    if (p == NULL) return;                 //L为空单链表时返回
    q = p->next;
    if (q == NULL) return;                 //L只有一个结点时返回
    r = q->next;                //r指向第3个结点
    if (r == NULL)                     //L只有一个结点时
    {
        L.head->next = q;
        q->next = p;
        p->next = NULL;
        return;
    }
    p->next = NULL;                     //原首结点p置为尾结点
    while (r != NULL)            //(p,q,r)指向的结点都存在时循环
    {
        q->next = p;                     //修改结点q的next指针
        p = q;                //(p,q,r)同步指针后移
        q = r;
        r = r->next;
    }
    q->next = p;                //修改结点q的next指针
    L.head->next = q;
}

template<typename T>
void Split(LinkList<T> &L, LinkList<T> &A, LinkList<T> &B) {
    LinkNode<T> *p = L.head->next, *q;             //p指向L的首结点
    LinkNode<T> *r = A.head;                 //r始终指向A的尾结点
    while (p != NULL)            //遍历L的所有数据结点
    {
        r->next = p;
        r = p;                //尾插法建立A
        p = p->next;                     //p后移一个结点
        if (p != NULL) {
            q = p->next;            //临时保存p结点的后继结点
            p->next = B.head->next;             //头插法建立B
            B.head->next = p;
            p = q;                //p指向q结点
        }
    }
    r->next = NULL;                    //尾结点next置空
}

template<typename T>
void Merge2(LinkList<T> &A, LinkList<T> &B, LinkList<T> &C) {
    LinkNode<T> *p = A.head->next;             //p指向A的首结点
    LinkNode<T> *q = B.head->next;             //q指向B的首结点
    LinkNode<T> *r = C.head;                 //r为C的尾结点
    while (p != NULL && q != NULL)        //两个单链表都没有遍历完
    {
        if (p->data < q->data)                 //将较小结点p链接到C的末尾
        {
            r->next = p;
            r = p;
            p = p->next;
        } else                //将较小结点q链接到C的末尾
        {
            r->next = q;
            r = q;
            q = q->next;
        }
    }
    r->next = NULL;                    //尾结点next置空
    if (p != NULL) r->next = p;                //将未归并完的结点链接到C的末尾
    if (q != NULL) r->next = q;
}

template<typename T>
void Commnodes(LinkList<T> &A, LinkList<T> &B, LinkList<T> &C) {
    LinkNode<T> *p = A.head->next;                //p指向A的首结点
    LinkNode<T> *q = B.head->next;                //q指向B的首结点
    LinkNode<T> *r = C.head;                    //r为C的尾结点
    while (p != NULL && q != NULL)            //两个单链表都没有遍历完
    {
        if (p->data < q->data)                     //跳过较小的p结点
            p = p->next;
        else if (q->data < p->data)                //跳过较小的q结点
            q = q->next;
        else                    //p结点和q结点值相同
        {
            auto *s = new LinkNode<T>(p->data);
            r->next = s;
            r = s;                    //将s结点链接到C的末尾
            p = p->next;
            q = q->next;
        }
    }
    r->next = NULL;                         //尾结点next置空
}




